Efficient Realization of Householder Transform through Algorithm-Architecture Co-design for Acceleration of QR Factorization

摘要

We present efficient realization of Householder Transform (HT) based QRfactorization through algorithm-architecture co-design where we achieveperformance improvement of 3-90x in-terms of Gflops/watt over state-of-the-artmulticore, General Purpose Graphics Processing Units (GPGPUs), FieldProgrammable Gate Arrays (FPGAs), and ClearSpeed CSX700. Theoretical andexperimental analysis of classical HT is performed for opportunities to exhibithigher degree of parallelism where parallelism is quantified as a number ofparallel operations per level in the Directed Acyclic Graph (DAG) of thetransform. Based on theoretical analysis of classical HT, an opportunityre-arrange computations in the classical HT is identified that results inModified HT (MHT) where it is shown that MHT exhibits 1.33x times higherparallelism than classical HT. Experiments in off-the-shelf multicore andGeneral Purpose Graphics Processing Units (GPGPUs) for HT and MHT suggest thatMHT is capable of achieving slightly better or equal performance compared toclassical HT based QR factorization realizations in the optimized softwarepackages for Dense Linear Algebra (DLA). We implement MHT on a customizedplatform for Dense Linear Algebra (DLA) and show that MHT achieves 1.3x betterperformance than native implementation of classical HT on the same accelerator.For custom realization of HT and MHT based QR factorization, we also identifymacro operations in the DAGs of HT and MHT that are realized on aReconfigurable Data-path (RDP). We also observe that due to re-arrangement inthe computations in MHT, custom realization of MHT is capable of achieving 12%better performance improvement over multicore and GPGPUs than the performanceimprovement reported by General Matrix Multiplication (GEMM) over highly tunedDLA software packages for multicore and GPGPUs which is counter-intuitive.